package Algorithm.Dp;
//https://leetcode-cn.com/problems/max-submatrix-lcci/
//最大子矩阵
public class Mianshiti_17_24 {
    class Solution {
        public int[] getMaxMatrix(int[][] matrix) {
            int max = matrix[0][0];

            int r1=0,c1=0,r2=0,c2=0;

            for(int i=0;i<matrix.length;i++){
                int[] sum = new int[matrix[0].length];
                for(int j=i;j<matrix.length;j++){
                    int ss = 0;//当前行前缀和（值会大于0）
                    int c = 0;
                    for(int k=0;k<matrix[i].length;k++){
                        sum[k] += matrix[j][k];

                        // 计算压缩后的当前行的最大子序列
                        if(ss + sum[k]>=sum[k]){
                            ss = ss + sum[k];
                        }else{
                            ss = sum[k];
                            c = k;
                        }

                        if(ss>=max){
                            max = ss;
                            c1 = c;
                            c2 = k;
                            r1 = i;
                            r2 = j;
                        }
                        max = Math.max(max, ss);
                    }
                }
            }

            return new int[]{r1,c1,r2,c2};
        }
    }
}
